class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def sum_digit(n: int)->int:
            sum_ = 0
            while n > 0:
                n, tmp = divmod(n, 10)
                sum_ += tmp
            return sum_

        visited = {(0,0),}
        for i in range(m):
            for j in range(n):
                if (i,j) not in visited and sum_digit(i)+sum_digit(j) <=k and \
                     ((i-1, j) in visited or
                     (i, j-1) in visited ):
                    visited.add((i,j))
        
        return len(visited)

if __name__ == '__main__':
    s = Solution()
    print(s.movingCount(3,1,0))